#include "data_structure/queue.h"
#include "data_structure/listo.h"
#include <stdlib.h>

struct Queue
{
    PQueue_Node begin;
    PQueue_Node end;
    bool (*equal)(PData_Val, PData_Val);
    bool (*less)(PData_Val, PData_Val);
    size_t list_size;
    size_t sizeof_type;
};

//创建并返回一个数据域大小为sizeof_type的节点
//创建失败返回NULL
static PQueue_Node queue_node_creat(int sizeof_type);

//从链表中分离出指定节点
static PQueue_Node queue_node_separate(PQueue thisc, PQueue_Node location);

//交换两个节点的位置
static void queue_node_swap(PQueue_Node node_r, PQueue_Node node_f);

//创建并返回一个数据域大小为sizeof_type的节点
//创建失败返回NULL
static PQueue_Node queue_node_creat(int sizeof_type)
{
    PQueue_Node new_node = (PQueue_Node)malloc(sizeof(Queue_Node));
    if (new_node == NULL)
        return NULL;
    new_node->data = (PData_Val)malloc(sizeof_type);
    return new_node;
}

//销毁一个节点
#define queue_node_destory(node) \
    {                            \
        free(node->data);        \
        free(node);              \
    }

//连接连个节点
//将src连接到dest的后面
#define queue_node_link(dest, src) \
    {                              \
        if (dest && src)           \
            dest->next = src;      \
    }

//设置一个节点的内容
#define queue_node_set(node, data, data_size)    \
    {                                            \
        if (node && data && data_size > 0)       \
            memcpy(node->data, data, data_size); \
    }

//从链表中分离出指定节点
static PQueue_Node queue_node_separate(PQueue thisc, PQueue_Node location)
{
    if (location == NULL || thisc == NULL)
        return NULL;

    if (thisc->begin == NULL)
        return NULL;

    if (location == thisc->begin)
    {
        PQueue_Node p = thisc->begin;

        if (p->next != NULL)
        {
            thisc->begin = p->next;
            thisc->list_size--;
        }
        else
        {
            thisc->begin = thisc->end = NULL;
            thisc->list_size = 0;
        }
        return p;
    }

    if (location == thisc->end)
    {
        PQueue_Node p = thisc->end;
        thisc->end->next = NULL;
        thisc->list_size--;
        return p;
    }

    PQueue_Node p = thisc->begin;
    PQueue_Node prev = p;

    while (p != location && p != NULL)
    {
        prev = p;
        p = p->next;
    }

    if (p == NULL)
        return NULL;

    if (prev && p->next)
    {
        queue_node_link(prev, p->next);
        thisc->list_size--;
        return p;
    }
    else
    {
        return NULL;
    }
}

PQueue queue_Creat(int sizeof_type)
{
    PQueue thisc = (PQueue)malloc(sizeof(Queue));
    thisc->begin = thisc->end = NULL;
    thisc->list_size = 0;
    thisc->sizeof_type = sizeof_type;
    return thisc;
}

void queue_destory(PQueue thisc)
{
    PQueue_Node p = thisc->begin, next;
    while (p)
    {
        next = p->next;
        queue_node_destory(p);
        p = next;
    }
}

//返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
PData_Val queue_front(PQueue thisc, PData_Val data)
{
    return thisc->begin->data;
}

//返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
PData_Val queue_back(PQueue thisc)
{
    return thisc->end->data;
}

//在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
void queue_push(PQueue thisc, PData_Val data)
{
    listo_push_back((PListO)thisc, data);
}

//删除 queue 中的第一个元素。
void queue_pop(PQueue thisc)
{
    PQueue_Node p = thisc->begin;
    thisc->begin = thisc->begin->next;
    queue_node_destory(p);
    thisc->list_size--;
}

//返回 queue 中元素的个数。
long queue_size(PQueue thisc)
{
    return thisc->list_size;
}

//如果 queue 中没有元素的话，返回 true。
bool queue_empty(PQueue thisc)
{
    if (thisc->list_size == 0)
        return true;
    else
        return false;
}

//的参数调用 T 的构造函数，在 queue 的尾部生成对象。
//将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap()
// void swap(PQueue thisc, PQueue q);
